//
//  niuke.swift
//  SFQuestion
//
//  Created by liusr on 2021/11/21.
//

import Foundation

//MARK: 补上letcode对应的k神的解析，做笔记，整理对应题目一般的解法
/*
 理解这个题用什么思路，套路，才能快速想起来这个怎么做
 */

//MARK: - 牛客网剑指offer
class NiuKe {
    
    //MARK: - 链表-----------------------
    
    //JZ 6 从尾到头打印链表
    /**
     输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

     示例 1：

     输入：head = [1,3,2]
     输出：[2,3,1]
     
     */
        func printListFromTailToHead ( _ head: ListNode?) -> [Int] {
            var stack = [Int]()
            var node = head
            while(node != nil) {
                stack.append(node?.val ?? 0)
                node = node?.next
            }
            return stack.reversed()
        }
        
        //JZ 25合并两个有序链表
        func Merge ( _ pHead1: ListNode?,  _ pHead2: ListNode?) -> ListNode? {
                // write code here
            //直接先搞个假的head
            let head = ListNode.init(0)
            var cur: ListNode? = head
            var p1 = pHead1, p2 = pHead2
            while p1 != nil && p2 != nil {
                if (p1?.val ?? 0) < (p2?.val ?? 0) {
                    cur?.next = p1
                    p1 = p1?.next
                } else {
                    cur?.next = p2
                    p2 = p2?.next
                }
                cur = cur?.next
            }
            if p1 == nil {
                cur?.next = p2
            }
            if p2 == nil {
                cur?.next = p1
            }
            //注意head的假头 返回 next
            return head.next
        }
        
        
        // JZ 24 翻转链表  终于自己写出来了
        // a -> b -> c -> d -> null  a<-b<-c<-d
        // null <- a <- b c->d
        func ReverseList ( _ head: ListNode?) -> ListNode? {
                // write code here
            //一次要拿着三个节点 保证串起来
            var pre: ListNode? = nil
            var cur = head
            
            while cur?.next != nil {
                let next = cur?.next//记下下一个
                cur?.next = pre//翻转一次
                pre = cur
                cur = next
            }//这个和下面的方法 就是判断条件有点差别
            cur?.next = pre
            return cur
        }
    
    // JZ 24 翻转链表 k神
    func ReverseList2 ( _ head: ListNode?) -> ListNode? {
        guard let headNode = head else { return nil }
        
        //A->B->C->D 实际上注意记住  当前的和上一个 让当前的指向上一个
        var curNode: ListNode? = headNode
        var preNode: ListNode? = nil
        
        while curNode != nil {
            let next = curNode?.next
            curNode?.next = preNode
            preNode = curNode
            curNode = next
        }
        //注意返回prenode  之前在while中做了判断break  还是k神厉害
        return preNode
        
    }
    
    // JZ52 两个链表的第一个公共结点
    //方法一 ： 先遍历一个链表记下所有的结点，在遍历第二个看是否集合中存在  有O(n)空间
    //方法二： 两个指针走
    func FindFirstCommonNode ( _ pHead1: ListNode?,  _ pHead2: ListNode?) -> ListNode? {
            // write code here
        /*
         A a长度 B b长度 c公共尾部长度
         headA 指针遍历完A后 转头遍历B  当走到node时 走的步数是  a+(b-c)
         headB 指针遍历完B后 转头遍历A  当走到node时 走的步数是  b+(a-c)
         
         所以 他俩重合的时候  上面的等式是成立的 如果c=0 就是不相交  要求返回null
         即使不相交，两个指针一直next 肯定有相等的时候 就是null的时候 返回就行了
         */
        
        var h1 = pHead1, h2 = pHead2
        while h1 !== h2 {
            //不能判断next走不通 走不到null
//            h1 = (h1?.next == nil) ? pHead2 : h1?.next
//            h2 = (h2?.next == nil) ? pHead1 : h2?.next
            h1 = (h1 == nil) ? pHead2 : h1?.next
            h2 = (h2 == nil) ? pHead1 : h2?.next
        }
        return h1
    }
    
    // JZ23 链表中环的入口结点
    /*
     快慢指针公式推导出来的
     
     */
    func EntryNodeOfLoop ( _ pHead: ListNode?) -> ListNode? {
            // write code here
        guard let head = pHead else { return nil }
        var fast: ListNode? = head, slow: ListNode? = head
        var meet = false
        while !meet {
            if fast == nil {
                return nil
            }
            fast = fast?.next?.next
            slow = slow?.next
            if fast === slow {
                meet = true
            }
        }
        
        fast = head
        while fast !== slow {
            fast = fast?.next
            slow = slow?.next
        }
        
        return slow
    }
    
    // JZ22 链表中倒数最后k个结点 输入一个链表，输出该链表中倒数第K个节点。
    //  双指针思路
    // LCR 021. 删除链表的倒数第 N 个结点. 要求删除的话 看力扣
    
    func FindKthToTail ( _ pHead: ListNode?,  _ k: Int) -> ListNode? {
            // write code here
        guard let pHead = pHead else {
            return nil
        }
        if k <= 0 {
            return nil
        }
        var p1: ListNode? = nil
        var p2: ListNode? = pHead//初值
        var sub = 1//临界判断容易出错  输入0  输入超过K的
        while sub < k && p2 != nil {
            sub += 1
            p2 = p2?.next
        }
        if p2 != nil {//能继续的话给初值
            p1 = pHead
        }
        while p2?.next != nil {
            p1 = p1?.next
            p2 = p2?.next
        }
        return p1
    }
    
    // JZ35 复杂链表的复制
    // 哈希表
    func Clone ( _ pHead: RandomListNode?) -> RandomListNode? {
            // write code here
        guard let head = pHead else {
            return nil
        }
        var p: RandomListNode? = head
        //RandomListNode 要实现可哈希 这里继承nsobject
        var dic = Dictionary<RandomListNode, RandomListNode>.init()
        while p != nil {
            //复制节点 忘了赋值  😭
            let node = RandomListNode.init(p?.label ?? 0, nil, nil)
            dic[p!] = node
            p = p?.next
        }
        p = head
        //注意头结点用新的
        let newHead: RandomListNode? = dic[p!]
        
        while p != nil {
            let newNode: RandomListNode? = dic[p!]
            if let next = p?.next {
                let newNext = dic[next]
                newNode?.next = newNext
            }
            
            if let random = p?.random {
                let newRandom = dic[random]
                newNode?.random = newRandom
            }
            
            p = p?.next
        }
        
        return newHead
    }
    
    // JZ76 删除排序链表中重复的结点  相同的都删掉 
    //下面的1 写成了去重
    //力扣83 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表
    func deleteDuplication1 ( _ pHead: ListNode?) -> ListNode? {
            // write code here
        var p = pHead
        while p?.next != nil {
            let node = p?.next
            if node?.val == p?.val {
                p?.next = node?.next
            } else {
                p = p?.next
            }
        }
        
        return pHead
    }
    //相同的都删掉
    func deleteDuplication ( _ pHead: ListNode?) -> ListNode? {
        guard let head = pHead else { return nil }
            // 有可能头结点就是重复的 那么头结点如何确定 ？ 创建一个哑节点  然后返回哑节点的下一个
        let dummy = ListNode.init(0)
        dummy.next = head//哑节点指向旧链表头 下面就能串起来
        
        var p = dummy.next//移动p
        var pre: ListNode? = dummy//记录前一个节点
        
        while p != nil {
            var node = p?.next
            if node?.val != p?.val {
                pre = p
                p = node
            } else {
                while node?.val == p?.val {
                    node = node?.next
                }
                pre?.next = node
                p = pre?.next
            }
        }
        
        return dummy.next
    }
    // JZ18 删除链表的节点
    func deleteNode ( _ head: ListNode?,  _ val: Int) -> ListNode? {
    // write code here
        
        guard let head = head else {
            return nil
        }

        //如果要删除的是第一个，提前判断
        if head.val == val {
            return head.next
        }
        
        var pre: ListNode? = head
        var cur: ListNode? = head.next
        while cur != nil && cur?.val != val {
            pre = cur
            cur = cur?.next
        }
        //while是双判断 所以要继续搞清楚条件
        if cur != nil {//说明找到了
            pre?.next = cur?.next
        }
        //相比之前写的更简洁 更熟悉了
        return head
    }
    
//MARK: - 树-----------------------
//JZ55 二叉树的深度
/*注意选择遍历方式：深度就是左子树深度+1 或者 右子树深度+1 取大的，就是说要先知道左右子树深度，适合用DFS后序遍历,递归求解
 后续：左右根
 思考:如果用循环栈怎么写
 */

func TreeDepth ( _ pRoot: TreeNode?) -> Int {
        // write code here
    guard let root = pRoot else { return 0 }
    let leftDepth  = TreeDepth(root.left)
    let rightDepth = TreeDepth(root.right)
    //就是利用后序遍历的这种思维，左右根  不一定是访问根 就是遍历到根的时候要根据题意做的事情
    //比如展开写
    let childDep = max(leftDepth, rightDepth)
    let dep = childDep + 1
    //return dep
    return max(leftDepth, rightDepth) + 1
}
/*
 层序遍历，广度优先搜索BFS用队列实现 ，循环处理
 
 */
func TreeDepthBFS ( _ pRoot: TreeNode?) -> Int {
    // 1、初始判空
    guard let root = pRoot else { return 0 }
    //2、初始化队列，直接加入根节点，作为第一层开始循环
    var queue = [root]
    var res = 0
    
    while queue.isEmpty == false {
        var list = [TreeNode]()
        for node in queue {//这里要注意和层序遍历不同的是  得遍历完这一行
            if let left = node.left {
                list.append(left)
            }
            if let right = node.right {
                list.append(right)
            }
        }
        queue = list
        //访问完一次queue深度加1
        res += 1
    }
    return res
}

//JZ77 按之字形顺序打印二叉树
/*
 第一层从左往右打印，第二层从右往左打印
 */

func Print ( _ pRoot: TreeNode?) -> [[Int]] {
        // write code here
    //考察层序遍历 通过奇偶控制遍历顺序
        guard let root = pRoot else { return [] }
        var result = [[Int]]()
        //第一层为1 奇数正序遍历
        var oddList = Array<TreeNode>()
        //偶数 倒序遍历
        var evenList = Array<TreeNode>()
        
        oddList.append(root)
        var tag = true
        while !oddList.isEmpty || !evenList.isEmpty {
            var tmpArr = [Int]()
            if tag {//从左往右
                for node in oddList {
                    tmpArr.append(node.val)
                    if let left = node.left {
                        evenList.append(left)
                    }
                    if let right = node.right {
                        evenList.append(right)
                    }
                }
                oddList.removeAll()
            } else {
                for node in evenList.reversed() {
                    tmpArr.append(node.val)
                    //注意添加顺序 右再左
                    if let right = node.right {
                        //注意放在最前面
                        oddList.insert(right, at: 0)
                    }
                    if let left = node.left {
                        oddList.insert(left, at: 0)
                    }
                }
                evenList.removeAll()
            }
            result.append(tmpArr)
            tag = !tag
        }
    //整段代码可以用1个数组优化，一次while遍历两行,https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/solution/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/
        return result
}
    //O（n）

// 优化：
    func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else { return [] }

        var result: [[Int]] = []
        var queue: [TreeNode] = [root]
        var leftToRight = true

        while !queue.isEmpty {
            var level: [Int] = []
            let count = queue.count

            for _ in 0..<count {
                let node = queue.removeFirst()
                level.append(node.val)

                if let left = node.left {
                    queue.append(left)
                }

                if let right = node.right {
                    queue.append(right)
                }
            }

            if !leftToRight {
                level.reverse() // 使用 reverse 方法实现之字形
            }

            result.append(level)
            leftToRight.toggle()
        }

        return result
    }

    //JZ54 二叉搜索树的第k个节点
    //力扣230，给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值
    
    var res = 0
    var k = 0
    
    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        self.k = k
        kthSmallDfs(root)
        return self.res
    }
    
    func kthSmallDfs(_ root: TreeNode?) {
        guard let root = root else { return }
        kthSmallDfs(root.left)
        //递归完左子树后检查
        if k == 0 {
            return
        }
        //遍历当前
        k = k - 1
        if k == 0 {//符合条件
            res = root.val
            return
        }
        kthSmallDfs(root.right)
    }
    
    
    //二叉搜索树特点可以联想到中序遍历后就是按顺序的，那么递归遍历到k就行了吧
    //我们按遍历二叉树的方式，每访问一个节点 就代表当前是个有效位 序号加一
//    func KthNode ( _ proot: TreeNode?,  _ k: Int) -> Int {
//    // write code here
//        var i = 1 //牛客明明说从0开始
//        var result = -1
//        KthNodeDfs(proot, &i, k, &result)
//        return result
//    }
    //复杂传递的引用太多
//    func KthNodeDfs ( _ proot: TreeNode?,  _ i: inout Int, _ k: Int, _ result: inout Int) {
//        
//        guard let root = proot else { return }
//        KthNodeDfs(root.left, &i, k, &result)
//        print(root.val, i)
//        
//        if i == k {
//            result = root.val
//            i += 1//只要访问就要加
//            return
//        }
//        //递归回来之后还会经过这里
//        if i >= k {
//            return
//        }
//        i += 1
//        KthNodeDfs(root.right, &i, k, &result)
//    }
    
    //letcode 54. 二叉搜索树的第k大节点和这个完全是反着的  看K神怎么提前返回的
    
    // JZ7 重建二叉树
    /*
     力扣 LCR 124. 推理二叉树 某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。请根据 preorder 和 inorder 的提示构造出这棵二叉树并返回其根节点。
     前序每一棵树第一个节点是root,中序找到这个root位置，就能根据中序确定这个root左右子树个数，
     进而在前序中又能找到左右子树的root,这样递归就能还原整棵树。
     所以我们保存前序数组即可，每一次递归，找到一棵树的root和这个节点对应的在中序中的左子树边界和右子树边界。当左大于右边的时候终止。   结束条件 自己走到最后悟吧，，，
     */
    var preOrder = [Int]()
    var inOrderDic:[Int: Int] = [:]//可以快速查找根节点在中序的位置
    func reConstructBinaryTree ( _ pre: [Int],  _ vin: [Int]) -> TreeNode? {
            // write code here
        preOrder = pre
        for (index, value) in vin.enumerated() {
            inOrderDic[value] = index
        }
        
        return reConstructBinaryTreeRe(0, 0, pre.count - 1)
    }
    //前序的根位置和  中序 左右子树位置，目的分冶算法找到左右子树根节点
    func reConstructBinaryTreeRe ( _ root: Int,  _ left: Int, _ right: Int) -> TreeNode? {
            // write code here
        if left > right {
            return nil
        }
        let rootValue = preOrder[root]
        let rootNode = TreeNode(rootValue)
        //找到root节点在中序的位置
        if let i = inOrderDic[rootValue] {
            //左子树长度，根据中序 i - left
            //左子树的根节点，根据前序，root + 1, 右子树根root + (i - left) + 1
            //左子树根节点对应的子树左右边界，left, i - 1
            rootNode.left = reConstructBinaryTreeRe(root + 1, left, i - 1)
            rootNode.right = reConstructBinaryTreeRe(root + (i - left) + 1 , i + 1, right)
        }
        return rootNode
    }
    
    //JZ26 树的子结构 LCR 143. 子结构判断
    //复杂度 两个树节点数目为M N   时间复杂度 M*N  空间最长的时候 单链 递归深度M
    func HasSubtree ( _ pRoot1: TreeNode?,  _ pRoot2: TreeNode?) -> Bool {
            // write code here
        guard let root1 = pRoot1 else { return false }
        guard let root2 = pRoot2 else { return false }//处理空树 空树不是子树 特殊处理
        var result = false
        if root1.val == root2.val {
            result = HasSubtreeDfs(root1, root2)
        }//当前相等才去开始递归下面！！！
        if result == false {
            result = HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2)
        }
        return result
    }
    
    func HasSubtreeDfs ( _ pRoot1: TreeNode?,  _ pRoot2: TreeNode?) -> Bool {
            // write code here
        //先判断p2他为空说明比较到最后了,空树不是子树 上面已经处理了
        if pRoot2 == nil {
            return true
        } else if (pRoot1 == nil) {//p1有可能一起遍历到最后 不能先判断 要跟着子树遍历走
            return false
        }
        if pRoot1?.val == pRoot2?.val {
            return HasSubtreeDfs(pRoot1?.left, pRoot2?.left) && HasSubtreeDfs(pRoot1?.right, pRoot2?.right)
        }
        return false
    }
    
    //JZ27 二叉树的镜像
    // LCR 144. 翻转二叉树
    func Mirror ( _ pRoot: TreeNode?) -> TreeNode? {
        guard let root = pRoot else { return nil }
        let tmpNode = root.left
        root.left = root.right
        root.right = tmpNode
        Mirror(root.left)
        Mirror(root.right)
        return root
    }
    
    //JZ32 从上往下打印二叉树
    //BFS广度搜索，层序遍历
    /*
     https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5/
     BFS 通常借助 队列 的先入先出特性来实现
     
     */
    func PrintFromTopToBottom ( _ root: TreeNode?) -> [Int] {
            // write code here
        var arr = [Int]()
        var queue = Array<TreeNode>()
        if let root = root {
            queue.append(root)
            while !queue.isEmpty {
                
                let node = queue.removeFirst()
                arr.append(node.val)
                if let l = node.left {
                    queue.append(l)
                }
                if let r = node.right {
                    queue.append(r)
                }
            }
        }
        return arr
    }
    
    //JZ33 二叉搜索树的后序遍历序列
    func VerifySquenceOfBST ( _ sequence: [Int]) -> Bool {
        if sequence.isEmpty {//牛客要求空树不符合
            return false
        }
        
        //自己写代码不是forin 就是 for...
        return VerifySquenceOfBSTRe(sequence, 0, sequence.count - 1)
    }
    
    func VerifySquenceOfBSTRe ( _ sequence: [Int], _ l: Int, _ r: Int) -> Bool {
        if l >= r {//子树数量不足1
            return true
        }
        
        var i = l//找右子树的第一个下标
        while sequence[i] < sequence[r] {
            i += 1
        }
        let m = i//记下来
        //判断右边是否都大于根
        while sequence[i] > sequence[r] {//肯定会找到相等的时候 不越界
            i += 1
        }
        //注意去掉根节点。 每一轮遍历找到一个根几点  N次递归 每一次复杂度 N^2
        return (i == r) && VerifySquenceOfBSTRe(sequence, l, m - 1) && VerifySquenceOfBSTRe(sequence, m, r - 1)
    }
    
    //MARK: JZ 28 对称的二叉树
    //LCR 145. 判断对称二叉树
    func isSymmetrical ( _ pRoot: TreeNode?) -> Bool {
                // write code here
            guard let root = pRoot else { return true }
        //这里比较特别 直接把根作为两个参数丢进去， 这样应该不对，往下走第一步会发现重复了一次递归
            return isSymmetricalDFS(root, root)
        //按力扣这个 就行了
        //return isSymmetricalDFS(root?.left, root?.right)
        }
        
        func isSymmetricalDFS(_ leftNode: TreeNode?, _ rightNode: TreeNode?) -> Bool {
            if leftNode == nil && rightNode == nil {
                return true
            }
            if leftNode == nil || rightNode == nil {
                return false
            }
            //这是node1?.val  (Int?)  如果两个都为nil就相等了  只不过前面都判断拦截了
            if leftNode?.val == rightNode?.val {
                return isSymmetricalDFS(leftNode?.left, rightNode?.right) && isSymmetricalDFS(leftNode?.right, rightNode?.left)
            }
            return false
        }
    
    // JZ34 二叉树中和为某一值的路径(二) LCR 153. 二叉树中和为目标值的路径
    //给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
    //本问题是典型的二叉树方案搜索问题，使用回溯法解决，其包含 先序遍历 + 路径记录 两部分
    // 回溯
    func FindPath ( _ root: TreeNode?,  _ expectNumber: Int) -> [[Int]] {
            // write code here
        var res: [[Int]] = Array<Array<Int>>.init()
        var path: [Int] = Array<Int>.init()
        
        func FindPathDFS(_ root: TreeNode?, _ expectNumber: Int) {
            guard let node = root else { return }
            path.append(node.val)
            let value = expectNumber - node.val
            if value == 0 && root?.left == nil && root?.right == nil {
                //叶子节点符合条件
                //swift的数组是值类型 不用担心对象移除的问题
                res.append(path)
            }
            FindPathDFS(root?.left, value)
            FindPathDFS(root?.right, value)
            //子树访问结束后递归栈会回到当前节点，移除当前节点，回到自己的上层
            path.removeLast()
        }
        FindPathDFS(root, expectNumber)
        return res
    }
    
    // JZ79 判断是不是平衡二叉树
    // 递归的办法 判断左右子树是不是平衡的
    func IsBalanced_Solution1 ( _ pRoot: TreeNode?) -> Bool {
            // write code here
        //利用深度 判断node是不是平衡 就要判断子树是不是平衡  做很多重复计算 O(n * logn)
        return abs(depth(pRoot?.left) - depth(pRoot?.right)) <= 1 && IsBalanced_Solution1(pRoot?.left) && IsBalanced_Solution1(pRoot?.right)
    }
    
    func depth(_ pRoot: TreeNode?) -> Int {
        guard let root = pRoot else { return 0 }
        return max(depth(root.left), depth(root.right)) + 1
    }
    
    // O（n） 最优解 从下往上判断，提前判断子树不平衡的就剪枝
    func IsBalanced_Solution ( _ pRoot: TreeNode?) -> Bool {
        return IsBalanced_SolutionDFS(pRoot) == -1 ? false : true
    }
    //一路走到最底部  如果此树不满足平衡 直接向上返回-1
    func IsBalanced_SolutionDFS (_ pRoot: TreeNode?) -> Int {
        guard let root = pRoot else { return 0 }
        let leftDep = IsBalanced_SolutionDFS(root.left)
        if leftDep == -1 {
            return -1
        }
        let rightDep = IsBalanced_SolutionDFS(root.right)
        if rightDep == -1 {
            return -1
        }
        if abs(leftDep - rightDep) <= 1 {
            return max(leftDep, rightDep) + 1
        }
        
        return -1
    }
    
    // JZ36 二叉搜索树与双向链表 牛客没要求循环
    //LCR 155. 将二叉搜索树转化为排序的双向链表 () 循环
    /*
     中序遍历 就是按顺序的，然后每一次递归遍历到当前后 处理pre和next的关系
     
     对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

     特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。
     */
    func Convert ( _ pRootOfTree: TreeNode?) -> TreeNode? {
            // write code here
        
        var head: TreeNode? = nil
        var pre: TreeNode? = nil
        //从最底部简单的三个节点的树理解
        func convertDfs(_ treeNode: TreeNode?) {
            guard let cur = treeNode else { return }
            convertDfs(cur.left)
            
            //访问到当前节点的时候，应该pre的下一个指向当前节点
            //那么一路向左访问左子树的时候还是没有pre就是头
            if pre == nil {
                head = cur
            } else {
                pre?.right = cur
                cur.left = pre
            }
            
            pre = cur
            convertDfs(cur.right)
        }
        
        convertDfs(pRootOfTree)
        //加上下面的两行就可以循环起来
        head?.left = pre
        pre?.right = head
        
        return head
    }
    
   // JZ8 二叉树的下一个结点 给出二叉树的其中一个节点 找出中序遍历下一个节点
    // 乍一看不难，情况要考虑全
    func GetNext ( _ pNode: TreeLinkNode?) -> TreeLinkNode? {
            // write code here
        guard let p = pNode else {
            return nil
        }
        let cur = p
        //如果结点有右子树, 右子树一直向左的结点
        while cur.right != nil {
            var node = cur.right
            while node?.left != nil {
                node = node?.left
            }
            return node
        }
        //没有右节点 是父节点的左子树
        if cur.right == nil && cur.next?.left === cur {
            return cur.next
        }
        
        if cur.right == nil &&  cur.next?.right === cur {
            var p_node = cur.next//父节点
            var p_p_node = p_node?.next
            while p_p_node != nil && p_node != nil {
                if p_p_node?.left === p_node {
                    return p_p_node
                }
                p_node = p_p_node
                p_p_node = p_node?.next
            }
        }
        
        return nil
    }

    //JZ78 把二叉树打印成多行
    func PrintBitree ( _ pRoot: TreeNode?) -> [[Int]] {
        //打印到多行，每一行放到一个数组
        //二叉树打印 bfs 广度搜索 借助队列的特性
        var res = Array<[Int]>()
        guard let root = pRoot else { return res }
        var queue = [root]
        while !queue.isEmpty {
            //队列不为空就循环
            //每一次遍历一层的个数，并持续把左右子树放到队列中
            var tmp = [Int]()
            for _ in 0..<queue.count {
                let node = queue.removeFirst()
                tmp.append(node.val)
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
            res.append(tmp)
        }
        return res
    }
    
}

//MARK: ---------------栈和队列--------------

// JZ9 用两个栈实现队列
class StackAndQueue {
    // JZ9 用两个栈实现队列
    var stack1 = [Int]()//push用
    var stack2 = [Int]()//pop用
    //这种题应该不会出 ，本身一个数组就能实现。就是模拟一下而已
    //记住栈只能一头进出 假如从数组的尾部
    func push ( _ node: Int) {
        stack1.append(node)
    }
//自己画一画就懂了
    func pop () -> Int {
        var value = 0
        //把stack1倒进stack2  在出
        if stack2.count > 0 {
            value = stack2.removeLast()
        } else {
            while stack1.count > 0 {
                stack2.append(stack1.removeLast())
            }
            value = stack2.removeLast()
        }
        return value
    }
    //本意应该是栈只能从头取值 每次用stack[0] 而不是removeLast方法
}

// JZ30 包含min函数的栈 LCR147 最小栈
public class SolutionStack {
    
    //数组的尾部作为顶
    
    
    //为什么要用last 符合栈的规律吗  swift append 和 add 是往什么位置放
    //append是往后加数据 所以last就是栈顶
    
    var arrA = [Int]()//作为一个正常的栈
    var arrB = [Int]()//作为排序的栈，不需要每次都把元素放进去排序，只要保证栈顶是最小的就好了
    
    func push ( _ value: Int) {
        // write code here
        
        arrA.append(value)
        if arrB.isEmpty {
            //注意： 等于要放进去！！！！保持同步，空的时候也得放进去
            arrB.append(value)
        } else if arrB.last != nil {
            let cur = arrB.last
            if cur! >= value {//新值，小于最小值栈顶数据
                arrB.append(value)
            }
        }
    }

    func pop () {
        let value = arrA.removeLast()
        //注意：只有相等才删除
        if value == arrB.last {
            arrB.removeLast()
        }
        
    }

    func top () -> Int {
        // write code here
        var value = 0
        if let cur = arrA.last {
            value = cur
        }
        return value
    }

    
    func min () -> Int {
        // write code here
        var value = 0
        if let cur = arrB.last {
            value = cur
        }
        return value
    }
    
    
   // JZ31 栈的压入、弹出序列  push  1 2 3 4 5    pop  4 5 3 2 1
    //输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序
    // https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solution/mian-shi-ti-31-zhan-de-ya-ru-dan-chu-xu-lie-mo-n-2/
    /*
     方法一：迭代入栈序列，循环中，每次入栈一个元素，再内嵌一个循环，如果入栈元素与弹出序列的第一个元素相同，则将入栈元素出栈，同时弹出序列减少一个元素，直至栈为空或者栈顶元素与弹出序列首元素不相等，当全部元素入栈后，等循环结束时判断栈是否为空，且弹出序列是否为空
     */
    
    
    /*
     时间复杂度 O(N)O(N)O(N) ： 其中 NNN 为列表 putIn 的长度；每个元素最多入栈与出栈一次，即最多共 2N2N2N 次出入栈操作。
     空间复杂度 O(N)O(N)O(N) ： 辅助栈 stack 最多同时存储 NNN 个元素。

     作者：Krahets
     链接：https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solutions/215152/mian-shi-ti-31-zhan-de-ya-ru-dan-chu-xu-lie-mo-n-2/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    //946. 验证栈序列
    // k神的思路永远那么简洁
    func IsPopOrder ( _ pushV: [Int],  _ popV: [Int]) -> Bool {
        
        var stack = [Int]()//辅助栈
        var i = 0//走pop序列
        //模拟一遍入栈与出栈 出栈的时候和popv对比
        for value in pushV {
            stack.append(value)
            while !stack.isEmpty && popV[i] == stack.last {
                stack.removeLast()
                i = i + 1
            }
        }
        
        return stack.isEmpty
    }
    
    //JZ73 翻转单词序列 “I am a    student”
    //倒序遍历双指针， 实际翻转两次字符串就行
    func ReverseSentence ( _ ReverseSentence: String) -> String {
        let reverseString = String(ReverseSentence.reversed())
        //这个应该可以去除多个空格
        let arr = reverseString.components(separatedBy: CharacterSet.whitespaces)
        var wordArr = Array<String>()
        
        for word in arr {
            if word.count > 0 {
                wordArr.append(String(word.reversed()))
            }
        }
        return wordArr.joined(separator: " ")
        //有个split高阶用法
    }
    
    //力扣超时
    func ReverseSentence2 ( _ ReverseSentence: String) -> String {
        if ReverseSentence.isEmpty {
            return ""
        }
        var s = ""
        var p1 = ReverseSentence.count - 1
        var p2 = p1
        //"  hello world!  "
        // " "
        while p1 >= 0 {
            //处理尾部空格  不然hello world那个有问题trimmingCharacters可以消除  就可以和k神一个解法了
            while p1 >= 0  && self.locationString(ReverseSentence, p1) == " "{
                p1 = p1 - 1
                p2 = p1
            }
            
            while p1 >= 0 && self.locationString(ReverseSentence, p1) != " " {
                p1 = p1 - 1
            }
            if p2 >= 0 {
                let word = self.subs(ReverseSentence, p1 + 1, p2)
                s.append(word)
                s.append(" ")
            }
            
        }
        if s.isEmpty == false {
            s.removeLast()
        }
        return s
    }
    
    func locationString (_ s: String, _ i: Int) -> String {
        let index = s.index(s.startIndex, offsetBy: i)
        let endIndex = s.index(after: index)
        let c = String(s[index..<endIndex])
        return c
    }
    
    func subs (_ s: String, _ i: Int, _ j: Int) -> String {
        let index = s.index(s.startIndex, offsetBy: i)
        let endIndex = s.index(index, offsetBy: j-i)
        let c = String(s[index...endIndex])
        return c
    }
    
    func solution_3(_ s: String) -> String {
            /**
            双指针超出时间限制，嵌套遍历和获取 String.index 对象会使用更多时间
            */
        //这个api把前后空格消除了 鸡贼
            let tmp = s.trimmingCharacters(in: .whitespacesAndNewlines)
            guard !s.isEmpty else {
                return s
            }
            
            var i=tmp.count - 1, j=i
            var words = [String]()

            while i >= 0 {
                while i >= 0 && String(tmp[tmp.index(tmp.startIndex, offsetBy: i)]) != " " {
                    i -= 1
                }
                
                let startIndex = tmp.index(tmp.startIndex, offsetBy: i+1)
                let endIndex = tmp.index(tmp.startIndex, offsetBy: j)
                
                words.append(String(tmp[startIndex...endIndex]))
                            
                while i >= 0 && String(tmp[tmp.index(tmp.startIndex, offsetBy: i)]) == " " {
                    i -= 1
                }
                
                j = i
            }
            
            return words.joined(separator: " ")
        }
    
}

// MARK: -动态规划
public class SolutionDPProblem {
    
    // JZ10 斐波那契数列
    /**
     f（n）= {
     
     0, n = 0
     1, n = 1
     f(n-1) + f(n-2), n > 1
     
     }
     
     */
    func Fibonacci ( _ n: Int) -> Int {
        var dp = [Int]()//第i个数的值是dp[i]
        dp.append(0)
        dp.append(1)//初值
        if n <= 1  {
            return dp[n]
        }
        for i in 2...n {
            dp.append((dp[i-1] + dp[i-2]) % 1000000007)//公式大数
        }
        return dp[n]
    }
    
    //优化空间复杂度
    func Fibonacci2 ( _ n: Int) -> Int {
        var dp0 = 0
        var dp1 = 1//根据公式只需要保存三个值就行 不需要数组
        var dpValue = 0
        if n == 0 {
            return dp0
        } else if n == 1 {
            return dp1
        }
        for _ in 2...n {
            dpValue = (dp0 + dp1) % 1000000007//公式
            dp0 = dp1
            dp1 = dpValue
        }
        return dpValue
    }
    
    // JZ69 跳台阶
    func jumpFloor ( _ number: Int) -> Int {
        /* 假定 0级的时候是 0 吧 有的看成1 公式能接起来
        1 级台阶： 1种
        2 级台阶： 一次上来 或者 一个一个上来  2种
         3级台阶： 从一级跳2下 + 从2级跳一下  3种
         4级台阶  从二级跳2下 + 从3级跳1下 5
         f(n) = f(n-1) + f(n-2)
        */
        
        if number <= 0 {
            return 0
        }
        // 代码不够简洁 但是顺着思路来可以理解
        var a = 1
        var b = 2
        if number == 1 {
            return 1
        } else if number == 2 {
            return b
        }
        var c = 0
        for _ in 3...number {
            c = (a + b) % 1000000007
            a = b
            b = c
        }
        return c
    }
    
    // JZ71 跳台阶扩展问题
    /*一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。1≤n≤20
     
     这个就是说 🐸在台阶n上，它的上一个台阶可以是前面任何的一个台阶，一下上来。每一个就代表一种
     f(n) = f(n-1) + f(n-2) + ... + f(1) + f(0)
     这个公式每一个dp[i] 都需要前面所有的数据 没法空间优化，继续推导
     f(n-1)展开就是f(n-2) + ... + f(1) + f(0)
     替换掉 最初的后面部分就是
     f(n) = 2 * f(n-1)
     
     初值
     f(1) = 1
     f(2) = 2
     f(3) = 4
     根据规律n得从2 开始，n<=1直接返回1就行
     
     继续找规律还可以看出n次方 暂时略
     
     */
    func jumpFloorII ( _ number: Int) -> Int {
        if number <= 1 {
            return 1
        }
        var a = 1
        var b = 1
        for _ in 2...number {
            b = a << 1//左移乘以2
            a = b
        }
        return b
    }
    
    //JZ42 连续子数组的最大和
    //https://labuladong.gitee.io/algo/3/24/81/
    func FindGreatestSumOfSubArray ( _ array: [Int]) -> Int {
        //与hot100中最长递增子序列类似  千万不要看着数组思维跳跃，推导！
        //dp[i] 含义: 以数组元素 array[i]结尾的最大子数组和是 dp[i], 那么dp[i]要么是自己加上前面数组要么是自己
        
        if array.isEmpty {
            return 0
        }
        
        var dp = Array.init(repeating: 0, count: array.count)
        dp[0] = array[0]
        for i in 1..<array.count {
            dp[i] = max(array[i], dp[i-1] + array[i])
        }
        return dp.max() ?? 0
    }
    
    
    //JZ63 买卖股票的最好时机(一) LCR 188. 买卖芯片的最佳时机
    //一维的还行，买卖多次的吃不消，labuladong 团灭股票买卖问题
    /*
     这种问题，暴力解法就是穷举：
     第一天买，第二天，3，4，。。天卖 就有 n-1种
     第二天买，3 4 5.。。卖就有  n - 2种
     
     n-1 + n-2 + ... + 1 就是  n(n-1) / 2种 复杂度就是O(n)
     仍然用动态规划做，注意设dp含义的规律
     
     dp[i] 为 以价格 prices[i]为结尾的子数组最大利润
     第i天的利润 就是前i-1天的利润 与 前i - 1天最小值与当天卖出价格的差值 中的最大值
     dp[i] = max(dp[i - 1], prieces[i]  - min(peices[0..i]) )
     
     
     */
    func maxProfit ( _ prices: [Int]) -> Int {
        if prices.isEmpty {
            return 0
        }
        //动态规划
        //减少时间复杂度 去掉数ra组，每次就要计算出dp后取大的
        var maxProfit = 0
        var cost = prices.first!
        for (i, e) in prices.enumerated() {
            if i == 0 {
                continue
            }
            maxProfit = max(maxProfit, e - cost)
            cost = min(cost, e)//这两行代码的顺序应该都行
        }
        
        return maxProfit
    }
    
    //JZ48 最长不含重复字符的子字符串 LCR 016. 无重复字符的最长子串
    //这个应该用滑动窗口算法？
    // 0 1 2 3 4 5 6 7 8 9
    // A B C A B E D E F C
    //这个用动态规划 不太对
    func lengthOfLongestSubstring ( _ s: String) -> Int {
        if s.isEmpty {
            return 0
        }
        //dp[j] 代表以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度
        //减少时间复杂度 去掉数组，每次就要计算出dp后取大的 用个tmp好理解吧
        //字符串取字符 太麻烦
        let characters = Array(s)
        var dic = [Character : Int]()
        var res = 0
        
        var tmp = 0 //相当于dp[j - 1]
        for (index, element) in characters.enumerated() {
            //还有自身作差，所以先放入dic
            
            if let i = dic[element] {
                //这一步就会发现dp推导有点不明确。。。
                tmp = (tmp < index - i) ? (tmp + 1) : (index - i)
            } else {
                tmp = tmp + 1
            }
            dic[element] = index
            res = max(tmp, res)//每次记录下最大的
        }
        
        return res
    }
    //滑动窗口
    func lengthOfLongestSubstring1 ( _ s: String) -> Int {
        if s.isEmpty {
            return 0
        }
        var left = 0
        var right = 0
        let characters = Array(s)
        var dic = [Character : Int]()
        var res = 0
        
        while right < characters.count {
            let c = characters[right]
            right += 1
            if let value = dic[c] {
                dic[c] = value + 1
            } else {
                dic[c] = 1
            }
            
            //看看dic里是否有重复字符了 也就是大于1
            while dic[c]! > 1 {
                let d = characters[left]
                left += 1
                //左移窗口 不断的去掉里面的值  直到去掉的这个值刚好是 c这个字母
                if let value = dic[d] {
                    dic[d] = value - 1
                }
            }
            res = max(res, right - left)
        }
        
        return res
    }
    //JZ47 礼物的最大价值 LCR 166. 珠宝的最高价值
    //矩阵 二维数组 问题
    
    // f(i,j)为棋盘左上角，走至单元格【i,j】礼物最大累积值.因为每一个格子的值都大于0，右下角肯定是最大的
    //f（i,j） = max(f(i-1,j), f(i,j-1)) + grid[i,j]
    func maxValue ( _ grid: [[Int]]) -> Int {
        if grid.isEmpty {
            return 0
        }
        //可以直接修改grid优化空间，本身Swift不支持修改，也为了理解过程 用一行数组做记录,一维数组也可以优化成min(m,n)
        
        let m = grid.count
        let n = grid[0].count
        var dp = Array.init(repeating: 0, count: n)
        //从上往下，从左往右的计算把数据往下落
        for i in 0..<m {
            for j in 0..<n {
                //判断就是按第一个 第一行 第一列 后面几列这样的顺序来的
                if i == 0 && j == 0 {//第一个
                    dp[j] = grid[i][j]
                } else if (i == 0) {//第一行
                    dp[j] = dp[j - 1] + grid[i][j]
                } else if (j == 0) {//第一列
                    //往下落dp[j]用上一个加上当前的值更新
                    dp[j] = dp[j] + grid[i][j]
                } else {
                    //已经落下的前一个 和上一行的取大的
                    dp[j] = max(dp[j-1], dp[j])  + grid[i][j]
                }
            }
        }
        return dp[n-1]
    }
    
    //JZ46 把数字翻译成字符串 LCR 165. 解密数字
    //letcode从0开始翻译的  牛客感觉有问题  0没有对应的  那中间遇到0怎么办
    /*类似于青蛙跳台阶，问的是多少种。条件就是相邻的数字能不能在0~25区间内
    dp【i】 以  第i个数字结尾  的数字最多的翻译种数
    dp[i] = dp[i-1] 当i-1和i不能翻译时
            = dp[i-2] + dp[i-1] 能翻译时
     */
    
    //例263
    func translateNum(_ num: Int) -> Int {
        let nums = String(num)
        if nums.isEmpty {
            return 0
        }
        if nums.count == 1 {
            return 1
        }
        var dp = Array.init(repeating: 0, count: nums.count + 1)//多用了一个空间
        //想一下,1个数字的时候最多1种，2个数字，最多是2种，由于我们求dp【2】要用到dp[0],根据dp[2] = 2
        // 定义dp【0】=1，就是
        
        //不用dp数组用  两个值  也好做  循环字符串的边界好处理些
        dp[0] = 1
        dp[1] = 1
        for i in 2...nums.count {
            //因为数组下标从1开始对应
            let startIndex = nums.index(nums.startIndex, offsetBy: i-2)
            let endIndex = nums.index(after: startIndex)
            let sub = String(nums[startIndex...endIndex])
            if sub >= "10" && sub <= "25" {
                dp[i] = dp[i-1] + dp[i-2]
            } else {
                dp[i] = dp[i-1]
            }
        }
            
        return dp[nums.count]
        }
    
}


//MARK: - 排序  查找
public class SortProblem {
    
    //JZ3 数组中重复的数字  可以看下442. 数组中重复的数据
    //用哈希表 或者数组set  findRepeatNumber 方法是另一个官方解法
    func duplicate ( _ numbers: [Int]) -> Int {
        if numbers.isEmpty {
            return -1
        }
        //把数据和下标存起来就行
        var dic = [Int: Int]()
        for (i, v) in numbers.enumerated() {
            if let _ = dic[v] {
                return v
            }
            dic[v] = i
        }
        return -1
    }
    
    //JZ51 数组中的逆序对  归并排序https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
    
    //JZ40 最小的K个数
    func GetLeastNumbers_Solution ( _ input: [Int],  _ k: Int) -> [Int] {
        //做法1
        //用快速排序(自己要会写) 排好之后 取出前k个
        let obj = Sort()
        var arr = input
        obj.QuickSort(&arr)
        let result = Array(arr.prefix(k))
        return result
    }
    //做法2  利用快排的思想
    //题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的 kk 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。
    //修改一下快排就能实现 
    
    func getLeastNumbers(_ arr: [Int], _ k: Int) -> [Int] {
        if arr.isEmpty || k > arr.count {
            return []
        }
        var varr = arr
        
        quickSort(&varr, 0, varr.count - 1, k)
        return Array(varr.prefix(k))
    }
    
    // 快排对于交换的写法有好几种 有的是都循环完了找到位置在交换。k神写法
    // 还有的直接先赋值不交换 最后交换。书上是这样，还有几种尾递归优化 大话结构
    // 写法不同 每一轮中枢得到的结果也不一样，但是整体左小右大是对的
    
    //对数组进行不完全的快速排序, 数组 左右边界 k个数
    func quickSort(_ arr: inout [Int], _ l: Int, _ r: Int, _ k: Int) {
        if l >= r {
            return
        }
        let tmp = arr[l]
        var low = l, high = r
        while low < high {
            //找中枢
            while low < high && arr[high] >= tmp {
                high = high - 1
            }
            arr[low] = arr[high]
            
            while low < high && arr[low] <= tmp {
                low = low + 1
            }
            arr[high] = arr[low]
        }
        //low就是本次中枢
        arr[low] = tmp
        //左边的太多了
        if low > k {
            quickSort(&arr, l, low - 1, k)
        }
        //不够k个 后部分继续排
        if low < k {
            quickSort(&arr, low + 1, r, k)
        }
        
    }
    
    //JZ53 数字在升序数组中出现的次数
    // 二分查找 力扣 34题
    //关于边界条件的判断，尽量靠齐 二分查找（BinarySearch）的写法，然后处理好边界情况
    func GetNumberOfK ( _ data: [Int],  _ k: Int) -> Int {
        // 例： 1 2 2 2 3 k = 2 ,  1 2 3 4 5  k = 3
        if data.isEmpty {
            return 0
        }
        var leftIndex = -1, rightIndex = -1
        //找左边界
        
        var low = 0, high = data.count - 1
        //low 在high右边终止  所以1 2 3 4 5  k = 3这个场景左边界最后是2
        while low <= high {
            let mid = low + (high - low) / 2
            if (data[mid] < k) {
                low = mid + 1
            } else if (data[mid] > k) {
                high = mid - 1
            } else {//找到后 左边界在左半区域
                high = mid - 1
            }
        }
        //找左边界就要返回low，那么就考虑low越界的情况 整体都没找到 low就是high+1
        if low >= data.count || data[low] != k {
            leftIndex = -1
        } else {
            leftIndex = low
        }
        //其实可以从左边界开始
        //找右边界
        low = 0
        high = data.count - 1
        
        while low <= high {
            let mid = low + (high - low) / 2
            if (data[mid] < k) {
                low = mid + 1
            } else if (data[mid] > k) {
                high = mid - 1
            } else {//找到后 左边界在左半区域
                low = mid + 1
            }
        }
        if high < 0 || data[high] != k {
            rightIndex = -1
        } else {
            rightIndex = high
        }
        
        if leftIndex != -1 && rightIndex != -1 {
            return rightIndex - leftIndex + 1
        }
        return 0
    }
    
    //JZ4 二维数组中的查找
    //二分查找的思想就是  二叉搜索树一样，因为有序所以每一次都能将数据规模左右分割
    //这个肯定不能从左边找，因为找一行或者一列还是无法分割
    func Find ( _ target: Int,  _ array: [[Int]]) -> Bool {
        
        if array.isEmpty || array[0].isEmpty {
            return false
        }
        var row = 0, column = array[0].count - 1
        //从左上角找起来
        while (row <= array.count - 1 && column >= 0) {
            if array[row][column] > target {
                //当前列过大，往前一列
                column = column - 1
            } else if array[row][column] < target {
                //当前行过小，往后一行
                row = row + 1
            } else {
                return true
            }
        }
        return false
    }
    
    //JZ11 旋转数组的最小数字
    func minNumberInRotateArray ( _ rotateArray: [Int]) -> Int {
            // 671234  4512223  451122222  2222412
        if rotateArray.isEmpty {
            return 0
        }
        //最小和最大数字之间的分割线，右边是小组 左边是大组,所以就每次和右边的数字比较一下
        var low = 0, high = rotateArray.count - 1
        while low < high {
            let mid = low + (high - low) / 2
            if ( rotateArray[mid] < rotateArray[high] ) {
                //在左半部分
                high = mid
            } else if ( rotateArray[mid] > rotateArray[high] ) {
                //在右半部分，而且肯定不是mid这个值
                low = mid + 1//有这里加一操作 while循环不用<=就行  注意点
            } else {
                //相等不确定左右，但是肯定在high的左边，所以可以 high = high - 1继续循环
                //或者直接线性搜索 不一定从哪个地方分开重复数字
                var x = low
                //不是high 或者和high相等 不用闭区间
                
                for i in (low + 1)..<high {
                    if rotateArray[i] < rotateArray[x] {
                        x = i
                    }
                }
                return rotateArray[x]
            }
        }
        return rotateArray[low]
    }
    
    //JZ44 数字序列中某一位数字
    func findNthDigit ( _ n: Int) -> Int {
    // write code here
        var n = n
        //确定这个数字有几位 是多少 要求的位 在这个数字中是第几位
        var digit = 1//数字位数
        var count = 9//一开始的最大数字
        var start = 1//当前数位起始值，0排除 因为有公式count = 位数乘以起始值 * 9
        while n > count {
            n = n - count
            start = start * 10
            digit = digit + 1
            count = start * digit * 9
        }
        //当前n就是在这个位数下的第几个 除以位数 看看第几个数
//        let se = Int(ceil( Double(n) / Double(digit) ))
        var se = n / digit
        if n % digit > 0 {
            se = se + 1
        }
        
        let num = start + se  - 1
        let nums = String.init(num).compactMap { c in
            Int(String(c))
        }
        
        let c = n % digit == 0 ? nums.count - 1 : n % digit - 1
        
        if c >= 0 && c < nums.count {
            return nums[c]
        }
        
        return 0
    }
    
    //JZ 38 字符串排列
    //k神交换字符的思路牛逼
    //官方解法
    var vis = Array<Bool>()
    var rec = Array<String>()
    func Permutation ( _ str: String) -> [String] {
        if str.isEmpty {
            return[]
        }
        vis = Array.init(repeating: false, count: str.count)
        var strArr = Array(str)
        strArr.sort()
        var tmpArr = Array<String>()
        self.perRecur(s: &strArr, i: 0, n: strArr.count, tmp: &tmpArr)
        return rec
    }
    
    func perRecur(s: inout Array<Character>, i: Int, n: Int, tmp: inout Array<String> ) {
        
        if i == n {
            rec.append(tmp.joined(separator: ""))
            return
        }
        
        for j in 0..<n {
            if vis[j] || (j > 0 && !vis[j-1] && s[j-1] == s[j]) {
                continue
            }
            vis[j] = true
            tmp.append(String(s[j]))
            self.perRecur(s: &s, i: i + 1, n: n, tmp: &tmp)
            tmp.removeLast()
            vis[j] = false
        }
    }
}

//MARK: - 位运算

//https://labuladong.github.io/algo/4/30/112/

public class BitOp {
    //JZ65 不用加减乘除做加法 写一个函数求两束之和 不能用加减乘除运算符
    // 异或得到不进位的结果，与操作 然后左移 得到进位 结果 两者再次相加
    func Add ( _ num1: Int,  _ num2: Int) -> Int {
        var a = num1
        var b = num2
        while b != 0 {
            let tmp = (a & b) << 1
            a = a ^ b
            b = tmp
        }
        return a
    }
    
    /*
     有符号整数通常用补码来表示和存储，补码具有如下特征：

     正整数的补码与原码相同；负整数的补码为其原码除符号位外的所有位取反后加 111。

     可以将减法运算转化为补码的加法运算来实现。

     符号位与数值位可以一起参与运算。

     作者：力扣官方题解
     链接：https://leetcode.cn/problems/add-without-plus-lcci/solutions/1718025/bu-yong-jia-hao-de-jia-fa-by-leetcode-so-pp8a/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    
    //JZ15 二进制中1的个数 
    //看一下 LCR 133. 位 1 的个数 不是这个解法
    //编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。
    
        /*
         
         func hammingWeight(_ n: Int) -> Int {
                 var count = 0
                 var value = n
                value > 0 {
                     value = (value - 1) & value
                     count += 1
                 }
                 return count
             }
         
         */
    
    func NumberOf1 ( _ n: Int) -> Int {
        var res = 0
        
        for i in 0...31 {
            if n & (1 << i) > 0 {
                res += 1
            }

        }
        
        // n和n-1相与 恰好把n的最低位的1  最低位的1 最低位的1 说三遍 置为0，所以循环与n-1操作即可
        //这样写越界  -2^31越界 输入的值是-1 这种整数也是没办法
//        var n = abs(n)
//        while n != 0 {
//            n = n & (n - 1)
//            res += 1
//        }
        
        
        return res
    }
    
    //JZ16 数值的整数次方  过 不看了
    func Power ( _ base: Double,  _ exponent: Int) -> Double {
        //快速降幂
        // x^n => (x^2)^(n/2)
        // 奇数就是 多乘一个x
        //每次循环 都通过这个公式分解
        if base == 0 {
            return 0
        }
        var res = 1.0
        var x = base
        if exponent < 0 {
            x = 1 / x
        }
        var b = abs(exponent)
        //跳出以前循环的思维，这是是不断在用底数换指数，遇到指数奇数的时候 就先乘上一个当前值
        while b > 0 {
            if b & 1 == 1 {//通过位运算判断奇数。b不断除以2取余肯定会取到1 再取余就会走进if
                res = res * x
            }
            x = x * x
            b = b >> 1
        }
        return res
    }
    
    //JZ56 数组中只出现一次的两个数字   力扣260. 只出现一次的数字 III
    
    /*
     一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

     数据范围：数组长度 ，数组中每个数的大小
     要求：空间复杂度 ，时间复杂度

     提示：输出时按非降序排列。
     
     */
    
    //这里是两个数字  哈希表  位运算
    func FindNumsAppearOnce ( _ array: [Int]) -> [Int] {
        /*
         -x 其实就是在x的值的基础上进行按位取反(~x)之后在增加1所得
         x&(-x)：保留二进制下最后出现的1的位置，其余位置置0（即一个数中最大的2的n次幂的因数
         x&(x-1)：消除二进制下最后出现1的位置，其余保持不变
         */
        
        if array.isEmpty {
            return []
        }
        var res = 0
        for num in array {
            res = res ^ num
        }
        //两个数不一样res肯定不是0 找出res某一位的1， 那么 num1和num2在这位上肯定一个是1 一个是0 然后根据这个条件，将数组中分开
        var value1 = 0, value2 = 0
        res = res & (-res)
        for num in array {
            if num & res == 0 {
                value1 = num ^ value1
            } else {
                value2 = num ^ value2
            }
        }
        
        if value1 > value2 {
            let tmp = value2
            value2 = value1
            value1 = tmp
        }
        
        return [value1, value2]
    }
    //JZ64 求1+2+3+...+n  不用乘除法不用if等分支语句
    func Sum_Solution ( _ n: Int) -> Int {
        //求和就是n和前n-1个数字的和.。利用 && 运算的特点进行递归
        var sum = n//用逻辑运算的短路性质
        (n > 0) && {
            sum = sum + Sum_Solution(n - 1)
            return true
        }()//用自动闭包实现
        return sum
    }
    
}

public class simulate {
    //JZ29 顺时针打印矩阵
    //思路清晰https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/mian-shi-ti-29-shun-shi-zhen-da-yin-ju-zhen-she-di/
    func printMatrix ( _ matrix: [[Int]]) -> [Int] {
            // write code here
        if matrix.isEmpty || matrix[0].isEmpty {
            return []
        }
        /*
         
         * * *
         * * *
         * * *
         
         */
        
        var res = [Int]()
        var top = 0, left = 0, right = matrix[0].count - 1, bottom = matrix.count - 1
        
        //循环走一遍，边界重合停止
        while true {
            //左到右
            for i in left...right {
                res.append(matrix[top][i])//top行i列
            }
            top += 1
            if top > bottom { break }//就不在继续了 不要等于号 走完一行减一行 走完一列减一列 边界代表未走的
            //每一步其实有俩边界限制着
            //上到下
            for i in top...bottom {
                res.append(matrix[i][right])
            }
            right -= 1
            if right < left { break }
            //右到左
            for i in (left...right).reversed() {
                res.append(matrix[bottom][i])
            }
            bottom -= 1
            if bottom < top { break }
            //下到上
            for i in (top...bottom).reversed() {
                res.append(matrix[i][left])//i行 left列
            }
            left += 1
            if left > right { break }
        }
        
        return res
    }
    
    //JZ61 扑克牌顺子
    /*
     1、排序 找出0的个数，然后顺序比较相邻数字之间差几？差的个数小于0的个数就能连起来
     2、转化：5个数字去除0 ，不能重复；最大数和最小数插值小于5
     
     现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
     有如下规则：
     1. A为1，J为11，Q为12，K为13，A不能视为14
     2. 大、小王为 0，0可以看作任意牌
     3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
     4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]
     
     */
    func IsContinuous ( _ numbers: [Int]) -> Bool {
            // write code here
        if numbers.isEmpty {
            return false
        }
        
        var res = false
        var mini = 14
        var maxnum = 0//取值也有水平 保证会错的初始值
        var numSet = Set<Int>()
        for i in numbers {
            if i == 0 {//为什么0可以舍去  因为就5张。
                continue
            }
            if numSet.contains(i) {
                //break不行 下面还会做差
                return false
            }
            numSet.insert(i)
            mini = min(mini, i)
            maxnum = max(maxnum, i)
        }
        res = maxnum - mini < 5
        return res
        
    }
}

public class other {
      
    
    //JZ5 替换空格
    func replaceSpace ( _ s: String) -> String {
    // write code here
        //这个就是遍历，遇到空格追加替换符。c++因为要用数组，提前计算好长度，两个指针倒序插入数据
        return s.replacingOccurrences(of: " ", with: "%20")
    }
    
    //JZ66 构建乘积数组  LCR 191. 按规则计算统计结果
    //b[i] = a[0] * a[i-1] * a[i+1] 可以把a[i]当做1 ，分开前后两部分相乘
    //因为要求一个数组结果 画出二维矩阵找规律
    func multiply ( _ A: [Int]) -> [Int] {
        if A.isEmpty {
            return [Int]()
        }
        var b = Array.init(repeating: 1, count: A.count)//b【0】在对角线位置 设为初值1 计算后半部分的时候会更新
        for i in 1..<A.count {
            b[i] = b[i-1] * A[i-1]
        }
        
        if A.count > 1 {//避免swift遍历越界
            var tmp = 1
            //从矩阵 下往上计算后半部分 最后一个b[len-1]在对角线忽略 从len-2开始。
            for i in (0...(A.count - 2)).reversed() {
                tmp = tmp * A[i + 1]//tmp代表要求的bi那行后半段  找规律
                b[i] = b[i] * tmp
            }
        }
        
        return b
    }
    
    //JZ50 第一个只出现一次的字符
    /*在一个长为n 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
    
    
    数据范围：0~10000，且字符串只有字母组成。
    要求：空间复杂度 O(n)，时间复杂度O(n)
     */
    //返回一个位置
    func FirstNotRepeatingChar ( _ str: String) -> Int {
        let s = Array(str)
        var idx = -1
        //返回一个位置不是返回那个字符，那么就在哈希表中多记录一个索引。swift元组很方便
        //存个数和布尔都行，布尔下次不用计算
        var dic = [Character:(Bool, Int)]()
        for (i, value) in s.enumerated() {
            dic[value] = dic.keys.contains(value) ? (false, i) : (true, i)
        }
        //要第一次出现一次的，所以遍历字符串不是遍历字典
        for c in s {
            if let (res, i) = dic[c], res == true {
                idx = i
                break
            }
        }
        
        return idx
    }
    
    //JZ39 数组中出现次数超过一半的数字  LCR 158. 库存管理 II（摩尔投票，清晰图解）
    func MoreThanHalfNum_Solution ( _ numbers: [Int]) -> Int {
        var nums = numbers
        var num = 0
        //1、排序取中位数
//        nums.sort()
//        num = nums[numbers.count / 2]
        //2、哈希表
//        var dic = [Int:Int]()
//        var count = 0
//        for i in nums {
//            if let v = dic[i] {
//                dic[i] = v + 1
//            } else {
//                dic[i] = 1
//            }
//            if let v = dic[i], v > count {
//                num = i
//                count = v
//            }
//        }
        //3、摩尔投票法
        /*
         Boyer-Moore 算法的本质和方法四中的分治十分类似。我们首先给出 Boyer-Moore 算法的详细步骤：

         我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；

         我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：

         如果 x 与 candidate 相等，那么计数器 count 的值增加 1；

         如果 x 与 candidate 不等，那么计数器 count 的值减少 1。

         在遍历完成后，candidate 即为整个数组的众数。

         作者：LeetCode-Solution
         链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-pvh8/
         来源：力扣（LeetCode）
         著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         */
        var c = 0
        var count = 0
        for i in nums {
            if count == 0 {
                c = i
            }
            if i == c {
                count += 1
            } else {
                count -= 1
            }
        }
        num = c
        return num
    }
    //调整数组顺序使奇数位于偶数前面
    func reOrderArrayTwo ( _ array: [Int]) -> [Int] {
        //双指针。但是如果要求奇数和奇数的原来顺序不变。偶数和偶数原来顺序不变只能用个辅助数组。
        //不过swift本身就需要var一个数组修改
        if array.isEmpty {
            return [Int]()
        }
        var nums = array
        var front = 0, behind = array.count - 1
        
        while front < behind {
            while array[front] & 1 == 1 && front < behind {
                front += 1
            }
            while array[behind] & 1 == 0 && front < behind {
                behind -= 1
            }
            //这种题都要举例子走一遍边界 。 上面循环后有可能就相交了
            if front < behind {
                nums.swapAt(front, behind)
                front += 1
                behind -= 1//少循环一次
            }
            
        }
        return nums
    }
    
    //JZ17 打印从1到最大的n位数
    //大数问题，但是既然题目数组要放下应该就不会超出
    
    let characters = ["0","1","2","3","4","5","6","7","8","9"]
    var res = [Int]()
    var nums = [String]()//几位数
    var n = 0//n位数
    func printNumbers ( _ n: Int) -> [Int] {
        self.n = n
        nums = Array.init(repeating: "0", count: n)
        dfsPrintNum(0)
        return res
    }
    
    /*
     //Int(numstr)这里自动就把001前面那些0去掉了。如果是以字符串的方式打印就要自己处理。
     //不用像k神那么麻烦，把0处理一下就行了, 1、可以直接处理numstr 去掉前面的0后返回再转int
     //想个办法能不能直接不把0放进去. 其实就是当前的0要不要放进去。数组？标记一下当前位的左边出现过非0数了。那么当前位的0就能放进去
     */
    
    func dfsPrintNum(_ x: Int) {
        if x == n {
            let numstr = self.move0(nums.joined(separator: ""))
            if numstr != "" {
                res.append(Int(numstr)!)
            }
            return
        }
        //第x位
        for i in characters {
            nums[x] = i
            dfsPrintNum(x+1)
        }
    }
    
    func move0(_ s: String) -> String {
        var newStr = ""
        var noZero = false
        for i in s {
            if noZero {
                newStr.append(i)
                continue
            }
            if i != "0" {
                noZero = true
                newStr.append(i)
            }
        }
        return newStr
    }
    
    //JZ45 把数组排成最小的数
    func PrintMinNumber ( _ numbers: [Int]) -> String {
        var nums = numbers.map {"\($0)"}
        nums.sort { a, b in
            a+b < b+a
        }
        
        return nums.joined()
    }
    
    //JZ57 和为S的两个数字
    func FindNumbersWithSum ( _ array: [Int],  _ sum: Int) -> [Int] {
        //数组是有序的
        var res = [Int]()
        var set = Set<Int>()
        for a in array {
            let b = sum - a
            if set.contains(b) {
                res.append(b)
                res.append(a)
                break
            }
            set.insert(a)
        }
        
        return res
    }
    
    func FindNumbersWithSum1 ( _ array: [Int],  _ sum: Int) -> [Int] {
        if array.isEmpty {
            return [Int]()
        }
        //数组是有序的
        //双指针降低空间复杂度
        var res = [Int]()
        var p1 = 0, p2 = array.count - 1
        while p1 < p2 {
            let s = array[p1] + array[p2]
            if s > sum {//大了 就让右边左移变小一点
                p2 -= 1
            } else if s < sum {
                p1 += 1
            } else {
                res.append(array[p1])
                res.append(array[p2])
                break
            }
        }
        return res
    }
    //JZ58 左旋转字符串
    func LeftRotateString ( _ str: String,  _ n: Int) -> String {
        //1。找出前半部分，后半部分 ，前翻转 + 后翻转 在整体翻转
        //2、
        return String(str.suffix(str.count - n)) + String(str.prefix(n))
    }
    
    //JZ74 和为S的连续正数序列  滑动窗口
    func FindContinuousSequence ( _ sum: Int) -> [[Int]] {
        //序列 1 2 3 4
        var res = Array<[Int]>()
        var p1 = 1, p2 = 2//p1 p2指针刚好和对应的数字相同便于计算了
        var s = p1 + p2//p1 p2形成一个窗口计算这之内的和
        while p1 < p2 {
            if s == sum {
                //p1 到 p2的数字添加到一个序列
                res.append(Array(p1...p2))
                s -= p1
                p1 += 1//操作顺序注意
            }
            if s < sum {
                p2 += 1
                s += p2
            }
            if s > sum {
                s -= p1
                p1 += 1
            }
        }
        return res
    }
    
    //JZ49 丑数
    func GetUglyNumber_Solution ( _ index: Int) -> Int {
        if index <= 0 {
            return 0
        }
        //通用方法 动态规划做
        //从小到大的顺序的第 n 个丑数 。动态规划理解题目最重要
        //三个指针指向最初的三个丑数
        var x = 0, y = 0, z = 0
        var dp = Array.init(repeating: 0, count: index)
        dp[0] = 1//dp里面的数都是丑数，不是12345序列，这是最开始没搞明白的
        for i in 1..<index {
            let n2 = dp[x] * 2, n3 = dp[y] * 3, n5 = dp[z] * 5
            let num = min(n2, n3, n5)
            if num == n2 {x += 1}
            if num == n3 {y += 1}
            if num == n5 {z += 1}
            dp[i] = num
        }
        return dp.last!
    }
    //JZ62 (圆圈中最后剩下的数)
    func LastRemaining_Solution ( _ n: Int,  _ m: Int) -> Int {
        //约瑟夫环问题 f(n) = ( f(n-1) + m ) % n
        //f(1) = 0长度为1的数字环剩余0
        var x = 0
        for i in 2...n {//要取到n
            x = (x + m) % i//x+m可能会超过长度 所以取余。理解取余 比如 7 个数 要找第三个 得重头开始，那么7 + 3边长了 模一下长度就回到头了
        }
        return x
        
        //如果暴力模拟一下呢
        
    }
    //JZ75 字符流中第一个不重复的字符
    //387. 字符串中的第一个唯一字符 给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
    
    var insertString = ""
    var strMap = [Character:Int]()
    
    func Insert ( _ ch: Character) {
            // write code here
        if let count = strMap[ch] {
            strMap[ch] = count + 1
        } else {
            strMap[ch] = 1
        }
        insertString.append(ch)
    }
    func FirstAppearingOnce () -> Character {
            // write code here
        var ch = Character.init("#")
        for c in insertString {
            if let count = strMap[c], count == 1 {
                ch = c
                break
            }
        }
        return ch
    }
    // JZ14 剪绳子  动态规划法
    //LCR 131 砍竹子 现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少
    //主站  343 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
    func cutRope ( _ n: Int) -> Int {
        let d = [0, 0, 1]
        if n < 3 {
            return d[n]
        }
        //dp[i] 表示将正整数 i拆分成至少两个正整数的和之后，这些正整数的最大乘积。
        var dp = Array.init(repeating: 0, count: n + 1)//长度为n的直接返回dp[n]
        dp[0] = 0
        dp[1] = 0
        dp[2] = 1
        for i in 3...n {
            for j in 2..<i {//当前长度下分成2  i - 2 ,3 i - 3，或者2 和 i- 2 并且i - 2是还能分的
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i-j]))//注意dp[i-j] 不是-1
            }
        }
        return dp[n]
    }
    
    func enumr() {
        //常见的一些遍历写法，字符串数组转换？
        var array = ["1","2","3"]
        var dic = ["a":1, "b":2, "c":3]
        var s = "123"
        
    }
    
}



/*
 
 01
 数据结构
 链表
 JZ6

 从尾到头打印链表
 简单
 29.12%
 JZ24

 反转链表
 简单
 38.68%
 视频题解
 JZ25

 合并两个排序的链表
 简单
 31.76%
 视频题解
 JZ52

 两个链表的第一个公共结点
 简单
 37.00%
 视频题解
 JZ23

 链表中环的入口结点
 中等
 35.66%
 视频题解
 JZ22

 链表中倒数最后k个结点
 简单
 32.04%
 视频题解
 JZ35

 复杂链表的复制
 较难
 23.38%
 JZ76

 删除链表中重复的结点
 中等
 21.95%
 JZ18

 删除链表的节点
 简单
 47.05%
 树
 JZ55

 二叉树的深度
 简单
 50.24%
 JZ77

 按之字形顺序打印二叉树
 中等
 28.46%
 视频题解
 JZ54

 二叉搜索树的第k个节点
 中等
 35.82%
 JZ7

 重建二叉树
 中等
 27.58%
 视频题解
 JZ26

 树的子结构
 中等
 25.41%
 JZ27

 二叉树的镜像
 简单
 64.89%
 视频题解
 JZ32

 从上往下打印二叉树
 简单
 29.85%
 JZ33

 二叉搜索树的后序遍历序列
 中等
 25.12%
 JZ82

 二叉树中和为某一值的路径(一)
 简单
 36.17%
 视频题解
 JZ34

 二叉树中和为某一值的路径(二)
 中等
 28.67%
 JZ36

 二叉搜索树与双向链表
 中等
 31.29%
 视频题解
 JZ79

 判断是不是平衡二叉树
 简单
 38.35%
 视频题解
 JZ8

 二叉树的下一个结点
 中等
 30.93%
 JZ28

 对称的二叉树
 简单
 32.34%
 视频题解
 JZ78

 把二叉树打印成多行
 中等
 34.03%
 JZ37

 序列化二叉树
 较难
 24.68%
 视频题解
 JZ84

 二叉树中和为某一值的路径(三)
 中等
 41.25%
 JZ86

 在二叉树中找到两个节点的最近公共祖先
 中等
 41.66%
 视频题解
 JZ68

 二叉搜索树的最近公共祖先
 简单
 41.26%
 视频题解
 队列 & 栈
 JZ9

 用两个栈实现队列
 简单
 41.22%
 视频题解
 JZ30

 包含min函数的栈
 简单
 34.72%
 视频题解
 JZ31

 栈的压入、弹出序列
 中等
 30.99%
 JZ73

 翻转单词序列
 简单
 21.83%
 JZ59

 滑动窗口的最大值
 较难
 26.86%
 视频题解
 02
 算法
 搜索算法
 JZ53

 数字在升序数组中出现的次数
 简单
 32.83%
 JZ4

 二维数组中的查找
 中等
 26.18%
 视频题解
 JZ11

 旋转数组的最小数字
 简单
 33.28%
 视频题解
 JZ38

 字符串的排列
 中等
 23.28%
 视频题解
 JZ44

 数字序列中某一位的数字
 简单
 24.22%
 动态规划
 JZ42

 连续子数组的最大和
 简单
 39.31%
 视频题解
 JZ85

 连续子数组的最大和(二)
 中等
 26.36%
 JZ69

 跳台阶
 简单
 40.17%
 视频题解
 JZ10

 斐波那契数列
 入门
 36.42%
 视频题解
 JZ19

 正则表达式匹配
 较难
 26.60%
 视频题解
 JZ71

 跳台阶扩展问题
 简单
 42.57%
 JZ70

 矩形覆盖
 中等
 36.62%
 JZ63

 买卖股票的最好时机(一)
 简单
 51.69%
 视频题解
 JZ47

 礼物的最大价值
 中等
 45.74%
 JZ48

 最长不含重复字符的子字符串
 中等
 29.71%
 JZ46

 把数字翻译成字符串
 中等
 16.63%
 视频题解
 回溯
 JZ12

 矩阵中的路径
 中等
 32.09%
 JZ13

 机器人的运动范围
 较难
 24.75%
 排序
 JZ3

 数组中重复的数字
 简单
 46.76%
 JZ51

 数组中的逆序对
 中等
 16.94%
 视频题解
 JZ40

 最小的K个数
 中等
 27.55%
 视频题解
 JZ41

 数据流中的中位数
 中等
 29.30%
 视频题解
 位运算
 JZ65

 不用加减乘除做加法
 简单
 45.48%
 JZ15

 二进制中1的个数
 简单
 35.43%
 JZ16

 数值的整数次方
 中等
 33.71%
 JZ56

 数组中只出现一次的两个数字
 中等
 51.50%
 视频题解
 JZ64

 求1+2+3+...+n
 中等
 43.20%
 模拟
 JZ29

 顺时针打印矩阵
 简单
 19.76%
 JZ61

 扑克牌顺子
 简单
 27.83%
 JZ67

 把字符串转换成整数(atoi)
 中等
 14.53%
 JZ20

 表示数值的字符串
 较难
 22.67%
 其他算法
 JZ66

 构建乘积数组
 简单
 41.43%
 JZ50

 第一个只出现一次的字符
 简单
 31.89%
 JZ5

 替换空格
 简单
 56.22%
 JZ21

 调整数组顺序使奇数位于偶数前面(一)
 中等
 51.14%
 JZ39

 数组中出现次数超过一半的数字
 简单
 32.67%
 视频题解
 JZ43

 整数中1出现的次数（从1到n整数中1出现的次数）
 中等
 36.04%
 JZ45

 把数组排成最小的数
 中等
 30.41%
 JZ49

 丑数
 中等
 23.43%
 JZ74

 和为S的连续正数序列
 中等
 29.77%
 JZ57

 和为S的两个数字
 中等
 30.91%
 JZ58

 左旋转字符串
 中等
 33.16%
 JZ62

 孩子们的游戏(圆圈中最后剩下的数)
 中等
 33.17%
 JZ75

 字符流中第一个不重复的字符
 中等
 33.87%
 JZ14

 剪绳子
 中等
 35.86%
 JZ81

 调整数组顺序使奇数位于偶数前面(二)
 简单
 51.51%
 JZ83

 剪绳子（进阶版）
 较难
 17.14%
 JZ17

 打印从1到最大的n位数
 简单
 45.61%
 
 */
